#include "util.hpp"

namespace std
{


template<class T, class V>
class Node
{
public:
    Node(const std::pair<T, V>& data)
        :data_(data), left_(nullptr), right_(nullptr)
    {}
public:
    Node<T, V>* left_;
    Node<T, V>* right_;
    std::pair<T, V> data_;
};


// 左边都比他小 右边都比他大
template<class T, class V>
class SortTree
{
public:
    SortTree()
        :root_(nullptr)
    {}
    void PushBack(const std::pair<T, V>& data)
    {
        if(nullptr == root_)
        {
            root_ = new Node<T, V>(data);
        }
        else
        {
            Node<T, V>* pos = root_;
            while(pos != nullptr)
            {
                if(data < pos->data_)
                {
                    if(pos->left_ == nullptr)
                    {
                        pos->left_ = new Node<T, V>(data);
                        return;
                    }
                    pos = pos->left_;
                }
                else
                {
                    if(pos->right_ == nullptr)
                    {
                        pos->right_ = new Node<T, V>(data);
                        return;
                    }
                    pos = pos->right_;
                }
            }
        }
    }
    
    void _PrePrint(const Node<T, V>* node)
    {
        if(node == nullptr)
        {
            return;
        }
        _PrePrint(node->left_);
        std::cout << node->data_.first << ": " << node->data_.second << " ";
        _PrePrint(node->right_);
    }
    void PrePrint()
    {
        _PrePrint(root_);
        std::cout << std::endl;
    }
    void _MidPrint(const Node<T, V>* node)
    {
        if(node == nullptr)
        {
            return;
        }
        std::cout << node->data_.first << ": " << node->data_.second << " ";
        _MidPrint(node->left_);
        _MidPrint(node->right_);
    }
    void MidPrint()
    {
        _MidPrint(root_);
        std::cout << std::endl;
    }
    const bool At(const T& key, V* const result)
    {
        Node<T, V>* tmp = root_;
        while(tmp != nullptr)
        {
            if(key < tmp->data_.first)
            {
                tmp = tmp->left_;
            }
            else if(key > tmp->data_.first)
            {
                tmp = tmp->right_;
            }
            else
            {
                *result = tmp->data_.second;
                return true;
            }
        }
        return false;
    }

private:
    Node<T, V>* root_;
};



};